MOD = 10 ** 9 + 7


class Solution:
    def numDecodings(self, s: str) -> int:
        size = len(s)

        # dp[i][0] = 从第i个开始匹配下一个，上一个数正好结束，之前有多少种方案
        # dp[i][1] = 从第i个开始匹配下一个，上一个数还未结束，之前有多少种方案
        dp = [[0, 0] for _ in range(size)]

        # 处理第1个字符
        if s[0] == "*":
            dp[0] = [9, 1]
        elif s[0] == "0":
            return 0
        else:
            dp[0] = [1, 1]

        # 处理后面的字符
        for i in range(1, size):
            if s[i] == "*":
                # 当前一个新的数
                dp[i][0] += dp[i - 1][0] * 9

                # 当前和上一位共同组成一个数
                if s[i - 1] == "1":
                    dp[i][0] += dp[i - 1][1] * 9
                elif s[i - 1] == "2":
                    dp[i][0] += dp[i - 1][1] * 6
                elif s[i - 1] == "*":
                    dp[i][0] += dp[i - 1][1] * 15

                dp[i][0] %= MOD

                # 当前和下一位共同组成一个数
                dp[i][1] = dp[i - 1][0]

            elif s[i] == "0":
                # *和上一位共同组成一个数
                if s[i - 1] == "1" or s[i - 1] == "2":
                    dp[i][0] = dp[i - 1][1]
                elif s[i - 1] == "*":
                    dp[i][0] = dp[i - 1][1] * 2
                else:
                    return 0

            else:
                # 当前是一个新的数
                dp[i][0] += dp[i - 1][0]

                # 当前和上一位共同组成一个数
                if s[i - 1] == "1" or (s[i - 1] == "2" and s[i] in {"1", "2", "3", "4", "5", "6"}):
                    dp[i][0] += dp[i - 1][1]
                elif s[i - 1] == "*":
                    if s[i] in {"1", "2", "3", "4", "5", "6"}:
                        dp[i][0] += dp[i - 1][1] * 2
                    else:
                        dp[i][0] += dp[i - 1][1]

                dp[i][0] %= MOD

                # 当前和下一位共同组成一个数
                dp[i][1] = dp[i - 1][0]

        return dp[-1][0]


if __name__ == "__main__":
    print(Solution().numDecodings("*"))  # 9
    print(Solution().numDecodings("1*"))  # 18

    # 测试用例194/217
    print(Solution().numDecodings("**"))  # 96
